/*
    leetcode 69
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 

输入：x = 4
输出：2

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
*/

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    int mySqrt(int x) {
        int left=0;
    	int right=x;
    	int ans=-1;
    	while(left<=right){
    		int mid=left+(right-left)/2;
    		if((long long)mid*mid<=x){
    			ans=mid;
    			left=mid+1;
			}else{
				right=mid-1;
			}
		}
		return ans;
    }
};